<?php 
/** 
 *二进制中1的个数
 *输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
 */



/**
 * 解法一：
 * n = 10  1010
 * n 先与1 进行&运算，判断最后一位是否为1,结果为1，记录，否则不记录，然后n右移一位，一直到n=0
 * 1010 & 0001 = 0 不记录，n右移
 * 0101 & 0001 = 1 记录，  n右移
 * 0010 & 0001 = 0 不记录，n右移
 * 0001 & 0001 = 1 记录，  n右移
 * 0000            n = 0 完结
 * 局限性，只适用于正数，复数右移，左边补1，死循环
 * 
 */
function NumberOf1_one($n)
{
	$count = 0;
    while($n) {
    	if ($n & 1) {
    		++$count;
    	}
    	$n = $n >> 1;
    }

    return $count;
}


/** 
 * [NumberOf1_two description]
 * n = 10
 * 为满足方法一负数的局限性
 * 可将1进行左移
 * 先与n进行与运算，n & 1 = 1 记录，然后1左移。直到n = 0；(需循环32次)
 * 
 * 
 * （整型数的字长和平台有关，尽管通常最大值是大约二十亿（32 位有符号）。64 位平台下的最大值通常是大约 9E18，除了 Windows 下 PHP 7 以前的版本，总是 32 位的。 PHP 不支持无符号的 integer。Integer 值的字长可以用常量 PHP_INT_SIZE来表示，自 PHP 4.4.0 和 PHP 5.0.5后，最大值可以用常量 PHP_INT_MAX 来表示，最小值可以在 PHP 7.0.0 及以后的版本中用常量 PHP_INT_MIN 表示 ）
 *
 * 
 */
function NumberOf1_two($n)
{
	$count = 0;
	$flag = 1;
    while($flag) {
    	if ($n & $flag) {
    		++$count;
    	}
    	$flag = $flag << 1;
    }
    return $count;
}
/** 
 * 解法三：
 * n - 1 相当于将n最右边的一个1 到 最右边的数取反，而这个1 的左边不变
 * 1010  - 1 = 1001
 *   **          **   取反
 * 11000 - 1 = 10111
 *  ****        ****  取反 
 * 所以推出 
 * n & (n - 1) = 将n最右边的一个1转化为0，能执行多少次这种操作，就是有多少个1
 * 例：
 * n = 10
 * 1010 & 1001 = 1000
 * 1000 & 0111 = 0000
 * 能执行两次，所有有两个1 
 */

function NumberOf1_three($n)
{
	$count = 0;
    while($n) {
    	++$count;
    	$n = $n & ($n - 1);
    }
    return $count;
}




echo NumberOf1_one(15);
echo NumberOf1_two(15);
echo NumberOf1_three(15);